
\chapter{Graphviz4Net}
\label{chap:graphviz}
Graphviz~\cite{graphviz:Online} is an open-source graph visualization tool, 
which we use in Patters4Net to create class diagrams. Graphviz is 
implemented as typical UNIX filter~\cite{uxfilter:Online}. For graphs representation, 
Graphviz uses special language called DOT. An example of DOT file is 
given in figure~\ref{fig:dotexample}. Graphviz expects a graph in the DOT language 
on the input, it generates the layout for given graph and then it renders 
it in a selected image format on standard output, or it can print the same 
graph in the DOT language on the standard output, 
but with attributes that provide information 
about the generated layout. Output format can be set up by command line 
option. Examples of the output are shown in the figure~\ref{fig:dotoutput}.
\begin{figure}[h]
	\begin{lstlisting}[language=C]
digraph G {
	node [shape=rect];
	node1 [label="A", width=2, height=1];
	node2 [label="B"];
	node3; node5;
	node1 -> node2 [label="Edge from A to B"];	
	node3 -> node1; node3 -> node5;
	node1 -> node5; node5 -> node2;
}
	\end{lstlisting}
	\label{fig:dotexample}
	\caption{An example of DOT file.}
\end{figure}

\begin{figure}[h]
\mbox{\includegraphics[width=35mm]{images/graph.jpg}}
\\
\begin{lstlisting}[language=C]
digraph G {
	node [label="\N", shape=rect];
	graph [bb="0,0,199,294"];
	node1 [label=A, width=2, height=1, pos="72,184"];
	node2 [label=B, width="0.75", height="0.5", pos="68,18"];
	node3 [width="0.75", height="0.5", pos="141,276"];
	node5 [width="0.75", height="0.5", pos="172,92"];
	node1 -> node2 [label="Edge from A to B", pos="..."];
	node3 -> node1 [pos="e,99.022,220.03 ..."];
	node3 -> node5 [pos="e,169.66,110.29 ..."];
	node1 -> node5 [pos="e,152.4,110.03 ..."];
	node5 -> node2 [pos="e,93.539,36.172 ..."];
}
\end{lstlisting}
	\caption{Graphviz output for graph from the figure~\ref{fig:dotexample}.}
	\label{fig:dotoutput}
	% \raisebox{1cm}
\end{figure}

To employ Graphviz in visualization of class diagrams, we have to convert our 
internal representation into the DOT language, then we have to parse the 
output of Graphviz and finally do some coordinates transformation and 
scaling to convert the layout in Graphviz representation to the WPF 
coordinates system. 

During the development, it turned out that this process can be 
modularized and we can segregate an independent library that provides 
.NET interface to the Graphviz filter and means to use the layout information 
generated by Graphviz for generating layouts in WPF or other GUI framework. 
Such library might be helpful for other projects than Patterns4Net. 
This resulted into the separate library called Graphviz4Net.

With Graphviz4Net users can define a graph and then display it into WPF 
application, or provide custom \emph{Layout Builder} for other GUI 
framework (e.g., Windows Forms). Graphviz (and thus Graphviz4Net) is capable of 
rendering graph clusters, curved edges with labels and arrows on both sides 
(arrows can have also labels) and much more. With built-in WPF 
\emph{Layout Builder}, graph node can any WPF control and even edges and 
labels rendering can be customized, although not as much as rendering of nodes.

\section{Public API}
Public API that Graphviz4Net provides can be divided up into two parts: 
graphs representation (input for Graphviz) and layout processing 
(output of Graphviz). 

\subsection{Graph representation}
Conversion of graphs into the input format of Graphviz works with 
interfaces \inlinecode{IGraph}, \inlinecode{ISubGraph} and \inlinecode{IEdge}, 
nodes may be of any type. However, for convenient use Graphviz4Net 
offers generic versions of these interfaces and classes that implement them. 
So the user of Graphviz4Net may: implement his own structures, he just 
have to make them implement interfaces mentioned above; or he may use the predefined 
generic classes. 

A graph aggregates list of it's nodes and sub-graphs, which aggregate list of 
their own nodes. Edges are aggregated by a graph object, but not by 
subgraphs, because edges may cross sub-graph boundaries. 

User may add custom attributes to the resulting DOT graph representation. 
The only thing which is needed for this is that the element (node, edge or 
subgraph) implements the \inlinecode{IAttributed} interface, which 
defines one property \inlinecode{Attributes} -- a name-value collection 
of DOT attributes. Default graph structures supplied with Graphviz4Net 
implement this interface and have properties for setting and getting the 
usual DOT attributes such as \inlinecode{Label}. 
These properties provide type-safe access to the 
\inlinecode{Attributes} collection, which can also be modified by hand in non 
type-safe manner to set up less usual DOT attributes.

\subsection{Layout builder}
When the graph is processed by Graphviz and the output is parsed by Graphviz4Net, 
we need to convert the layout data to actual elements on the screen or in the 
generated picture. For this purpose the \pattern{Builder} pattern is employed. 
Graphviz4Net takes care of parsing the output, but when it has a piece of layout 
information for example "the position of the node with id 2 is [34, 55]", it 
passes this piece of information to the appropriate method of the \emph{Layout Builder} 
and this method may then create an element on the screen or anything else.

Next to the graphical elements building, the \emph{Layout Builder} is 
also responsible for suppling the sizes of the graph nodes, so that Graphviz 
can produce precise layout where nodes and edges do not overlap.

Graphviz4Net has one built-in \emph{Layout Builder} for WPF applications 
(we suppose that it could build Siverlight layouts as well, 
however it hasn't been tested yet). Users even don't have to directly use 
this \emph{Layout Builder}, the whole process of layouting is encapsulated in 
the \inlinecode{GraphLayout} WPF control. The only thing needed is to set up 
the dependency property \inlinecode{Graph} and provide data templates for 
nodes types.

\section{Architecture}
\subsection{DOT parsing.}
One of the tasks Graphviz4Net has to deal with is parsing the Graphviz output, 
which is a text in the DOT language. We developed a 
parser based on ANTLR parser generator (\cite{antlr:Online}) 
that is able to parse most of the 
the DOT language constructs that Graphviz produces as an output 
(it is a subset of the full DOT language, because we know that some DOT 
constructs, e.g., comments are never produced by the Graphviz).

Graphviz provides also plain-text output format, which is line oriented 
language suitable for parsing. However, we found out that this format 
does not support some features of Graphviz that we wanted to support in 
our library (e.g., node clusters).

\subsection{WPF Support}
Graphviz generates layout information in format where lengths are in 
inches, coordinates are in points ($1/72$ of an inch) and refer to the center 
of the element, the origin $[0,0]$ is in the bottom left corner, 
coordinate values increase up and to the right and curved edges 
are represented as B-spline points. All these pieces have to be adopted to the 
WPF formats where e. g. positions can refer to one of the corners of the 
element, but not to it's center. There are two possible approaches for this 
adoption: convert all the values; or make use of render transformations in 
WPF to overcome the problem of different coordinate systems, but other 
values would still have to be converted. In Graphviz4Net we went with the 
first option, because the render transformations might slow down the 
application and there is not much difference between the two 
approaches in the amount of work.

The main work of the WPF \emph{Layout Builder} is to adopt the values 
from Graphviz to WPF format. It gets a \inlinecode{Canvas} instance as 
a constructor parameter and it places all the elements into this 
\inlinecode{Canvas} using \inlinecode{Canvas} dependency 
properties \inlinecode{Top} and \inlinecode{Left}. The decision 
which WPF elements should be used for the graphical representation of 
each of the elements in the graph 
is leaved to an \pattern{Abstract Factory} object, which is also a parameter 
of the constructor of the WPF \emph{Layout Builder}. In the default 
implementation of the factory for nodes we just create ContentPresenter 
with Content set to the node type. This enables users of Graphviz4Net to 
define a data template for each type of a node (remember that nodes may 
be of any type, so a data structure with complex information or 
just simple string for label may be used).

The WPF \emph{Layout Builder} should also provide the sizes of the nodes 
for Graphviz. For this purpose it uses the WPF layout system. Every 
\inlinecode{FrameworkElement} has a method \inlinecode{Measure(availableSize)}, 
in which the \inlinecode{FrameworkElement} should determine it's size 
requirements by using an \inlinecode{availableSize} parameter. 
For the \inlinecode{availableSize} we use \inlinecode{double.Infinity} and thus 
allow the element to set up any size. Desired size of the element is then 
accessible via property \inlinecode{DesiredSize} and the transformed 
value of this property is given to Graphviz.

Graphviz4Net provides also a WPF control that encapsulates this logic. 
The control uses standard WPF mechanisms of dependency properties 
and templates.

